/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/count-primes
   @Language: C++
   @Datetime: 20-01-06 17:28
   */

// Method 1, prime selection, 96ms 59%, 8.6MB 74%
class Solution {
public:
	int countPrimes(int n) {
		vector<bool> primes(n, true);
		int count=0;
		for(int i=2; i<n; ++i){
			if(!primes[i]) continue;
			++count;
			for(int j=i+i; j<n; j+=i)
				primes[j]=false;
		}
		return count;
	}
};
